package Hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-01-12 22:02
 */
public class findDisappearedNumbers448 {
    /**
     * 448. 找到所有数组中消失的数字
     * 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
     * 1、排序后，遍历查找
     * 2、直接用boolean数组记录是否出现过
     * */
    public List<Integer> findDisappearedNumbers1(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<Integer> res=new ArrayList<>();
        int cur=1,i=0;
        while (i< n){
            if (nums[i]>cur){
                res.add(cur);
                cur++;
            }else if (nums[i]==cur){
                i++;cur++;
            }else {
                i++;
            }
        }
        while (cur<= n){
            res.add(cur++);
        }
        return res;
    }
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n=nums.length;
        boolean[] isvisited=new  boolean[n+1];
        for (int num:nums) {
            isvisited[num]=true;
        }
        List<Integer> res=new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (!isvisited[i]){
                res.add(i);
            }
        }
        return res;
    }
}
